package junior.DynamicProgramming动态规划;

public class 背包01 {

    public static void main(String[] args) {
        int N = 3; //商品数量
        int C = 4; //背包容量
//      初始化数据(注意适配边界)
        int[] weight = {0,1  ,4  ,3};  //商品容量
        int[]  price = {0,150,300,200};  //商品重量
        int[][] st = new int[N+1][C+1]; //控制边界，状态转移数阵，行：对应商品   列：对应重量(表示在前i个物品中能够装入容量为j的背包中的最大价值)
        int[][] path = new int[N+1][C+1]; //标记路径，当背包有剩余空间，且放入商品时，标记为1（放入商品后最优解 大于 原背包商品最优解）
//      状态转移方程（核心）
        for (int i = 1; i < N+1; i++) {   //边界默认初始化为0:0物品，0商品
            for (int j = 1; j < C+1; j++) {  // j控制背包容量递增，试探放入商品
                if (weight[i] > j)  //商品重量大于背包可用重量
                    st[i][j] = st[i-1][j];  //st[i-1][j] 当前背包容量最优价值
                else {
//                    st[i][j] = Math.max(price[i]+st[i-1][j-weight[i]],st[i-1][j]);//装入物品价值+背包剩余容量最优价值   >=<    当前背包容量最优价值（区最大值）
                    if(price[i]+st[i-1][j-weight[i]] >= st[i-1][j]) {  //标记前提，有空余容量，且最优价值更大
                        st[i][j] = price[i]+st[i-1][j-weight[i]];
                        path[i][j]=1;  //标记
                    }else
                        st[i][j] = st[i-1][j];
                }
            }
        }
        System.out.println("最大价值："+st[N][C]);
//        打印状态转移数组
        System.out.println("打印状态转移数组:");
        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < C + 1; j++) {
                System.out.print(st[i][j]+"\t");
            }
            System.out.println();
        }
//        打印标记数组
        System.out.println("打印标记数组:");
        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < C + 1; j++) {
                System.out.print(path[i][j]+"\t");
            }
            System.out.println();
        }
//        打印放入的商品
        System.out.println("打印放入的商品:");
        int i = N;
        int j = C;
        while (i>0 && j>0){
            if (path[i][j] == 1){
                System.out.println(i+" 号商品放入背包");
                j = j-weight[i];   //背包容量减去当前物品的质量
            }
            i--;  //去掉改商品
        }
        
    }
}
